package DFS;

import java.util.LinkedList;
import java.util.List;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-22
 * Time:14:34
 * Text：22. 括号生成
 */
public class Text10 {
    int left=0,right=0;
    List<String> t1;
    StringBuffer str;
    int m;

    void add(){
        if(left==m && right==m)
            t1.add(str.toString());
        else if(left<m){
            for(int i=left;i<m;i++){
                str.append("(");
            }
            t1.add(str.toString());

        }else if(right<m){
            for(int i=right;i<m;i++){
                str.append(")");
            }
            t1.add(str.toString());
        }
    }
    void dfs(){
        if(left==m || right==m){
            StringBuffer str2=new StringBuffer(str);
            add();
            str=str2;
            return;
        }
        if(right > left){
            return;
        }else if(left == right){
            str.append("(");
            left++;
            dfs();
            left--;
            str.deleteCharAt(str.length()-1);
        }else if(left>right){
            str.append("(");
            left++;
            dfs();
            left--;
            str.deleteCharAt(str.length()-1);
            str.append(")");
            right++;
            dfs();
            right--;
            str.deleteCharAt(str.length()-1);
        }
    }
    public List<String> generateParenthesis(int n) {
        t1=new LinkedList<>();
        str=new StringBuffer();
        m=n;
        dfs();
        return t1;
    }

    public static void main(String[] args) {
        Text10 t=new Text10();
        t.generateParenthesis(3);
    }
}
